Programmable logic arrays (PLAs) have become a popular element in the implementation of high density, functionally complex very large scale integrated (VLSI) circuits. It is expected that the use of PLAs in future IC designs will be even more pervasive. There are two basic reasons for the popularity and widespread use of PLAs. First, PLAs are simple in design and regular in structure, which reduces the complexity of the overall chip design. In addition, this regularity and simplicity lends itself to automation of the design process. Second, many attempts have been made to further reduce the hardware and silicon area required to implement a PLA design.
Despite the regularity of the structure and the simplicity of the design, in general, the testing of PLAs remains a difficult task. Test pattern generation for PLAs is a laborious and involved process. Even with a powerful test pattern generator program and under some modest fault assumptions (i.e., single stuck-at or bridging faults) complete fault coverage cannot be guaranteed.
Before an explanation of the problems inherent in testing PLAs is given, it may be useful to define some terms by reference to FIG. 1 of the drawings which shows a schematic of a prior art PLA 10. A programmable logic array 10 may be considered to be a two level NOR-NOR matrix of gates preceded by a one-bit decoder on each input. The PLA 10 shown in the Figures is a NOR-NOR PLA, but may be viewed as an effective AND-OR PLA. To simplify the notation, the first level of NOR gates will be referred to as a first level array 12. As mentioned, in one form, the first level array 12 may be connected to form a set of AND gates 14. Likewise, the second level array 16 may be connected to form a set of OR gates 18. However, PLA 10 may be easily modified to implement one of the other three styles of PLA, AND-OR, OR-AND, and NAND-NAND.
In general, the first level array 12 has N input lines 20, X.sub.1 -X.sub.N, for receiving N normal input signals, and M output lines, Y.sub.1 -Y.sub.M, 22 for providing M product terms. The second level array 16 has M input lines 22 for receiving the M product terms and P output lines 24, Z.sub.1 -Z.sub.P, for providing P output signals. The term n will be used to refer to the number of inputs to any particular gate in the first level of the PLA, whereas m will be used to refer to the number of outputs that any particular gate feeds. Subscripts k and L will be used to refer to any general AND or OR gate, respectively.
Under the single stuck fault assumption, a single n-input gate has 2(n+1) potential faults, including a stuck high fault and a stuck low fault on the output and on each input. All of these faults can be detected by n+1 tests. For the entire PLA, the total number of tests required will be designated as M(2N) tests. For a NOR gate, all inputs set to ZERO (the non-controlling value, i.e. one which will not finally cause a change in output) stimulates the stuck high fault on the inputs and the stuck low fault on the output. This is called the exact decode test. Individually setting each one of the inputs high while holding all others low stimulates the stuck low fault on the input under test and the stuck high fault on the output.
To detect a fault in PLA 10, it must be stimulated by an appropriate input test vector and propagated to one of the P outputs 24. To sensitize a path from a particular AND.sub.k through OR.sub.L to its output, we must set all of the other m-1 inputs to OR.sub.L to their non-controlling value. Since the N inputs fan out into various product terms 22 which recombine as inputs to the OR plane 16, this test problem is non-trivial. In fact, algorithmically it is non-polynomially or np complete, meaning that the test problem is not solvable by polynomial techniques and must be solved by exhaustively applying all possible permutations of test vectors.
In general, the test problem requires a judicious setting of the "don't cares" in an input test vector in order to propagate the fault. It is often not possible to propagate an AND fault through every OR gate it feeds. Thus, the path to sensitize becomes an additional variable. For a non-embedded PLA this is merely a computationally intense problem. However, when the inputs to the PLA are embedded, the problem is much more complex. A PLA 10 is "embedded" in a circuit when other circuitry is interposed between the inputs 20 to the PLA 10 and the input paths available for external stimulation. Typically, the vectors applied to the external inputs will not be the same as the required PLA inputs since the external signals must be propagated through--and changed by--the intervening logic. If this logic is sequential, it may be necessary to apply several external inputs to produce one test vector.
Embedded PLAs will also typically have a reduced universe of input vectors. This reduction is a function of the intervening logic and is typically far from obvious. Reducing the universe virtually rules out computer automated test pattern generation (ATPG), as many of the ATPG vectors will be impossible to produce at the embedded PLA inputs. Furthermore, some faults may be impossible to detect by any test in this reduced universe.
One method of dealing with the problem of reconvergent fan-out is to insert additional control points on the product terms 22. In this technique, all product terms 22 except for the output of the AND gate 14 under test are pulled low. This sensitizes a path to all outputs fed by this AND gate 14.
Several authors have proposed using an M-bit shift register for Product Term Control (PTC). If the shift register (SR) is connected to the PLA such that a ONE in a SR bit disables its associated product term 22, then walking a ZERO through a field of ONEs in the SR will enable each product term 22, one at a time. Unfortunately, the area required for a SR of this type is prohibitive for large volume VLSI production.
An alternative proposal is the decoder depicted in FIG. 1 and described by S. Bozorgui-Nesbat, et al. in "Lower Overhead Design for Testability of Programmable Logic Arrays," IEEE 1984 International Test Conference (publication of papers), pp. 856-865. Here, log.sub.2 (M) additional inputs 28 are applied to a one-of-M decoder 26. The outputs of this decoder 26 are used exactly as the SR outputs were previously used. Applying the proper sequence of vectors to the additional inputs 28 will walk a ZERO through a field of ONEs on the decoder 26 outputs 22. However, this requires additional paths to be routed to the PLA 10 and additional pins for these inputs, causing a potentially large area overhead. Even the authors of the cited article admit that this method would not be suitable for built in self test (BIST) techniques.
Neither of these two methods are BIST. Both pay an area penalty merely to simplify test pattern generation. The test pattern simply consists of all the n+1 tests for each AND gate 14. Propagating these tests from the input pins to an embedded PLA may be difficult or impossible.
Recently, a PLA test method has been suggested which uses a shift register on the PLA inputs and a second shift register on the product terms by R. Truer, et al. in "Name and Implementation of a New Built in Self Test PLA Design," Design and Test, Report No. 84.14 from McGill VLSI Design Laboratory, 1984. This test apparatus, although on the chip, is slow in its test routine. In addition, a conventional program term control register is still used in this design, which yet occupies a large amount of chip area.
For an integrated circuit, the simplest on-chip test vector generator is a linear feedback shift register (LFSR). By generating 2.sup.N -1 vectors (the all ZERO case will not occur), this approach nearly exhaustively tests the PLA. The LFSR requires no additional PTC logic. However, most of the 2.sup.N -1 vectors generated by the LFSR serve no useful purpose. Thus, although the area overhead is low, the time overhead is unacceptable for PLAs with many inputs.
Thus, there remains a need for a BIST for PLAs which is acceptable in terms of time and area overhead. This need is particularly strong in the case of embedded PLAs.